Types of wireless networks include infrastructure-based wireless networks and ad hoc wireless networks.
An infrastructure-based wireless network typically includes a communication network with fixed and wired gateways. Many infrastructure-based wireless networks employ a mobile unit or host which communicates with a fixed base station that is coupled to a wired network. The mobile unit can move geographically while it is communicating over a wireless link to the base station. When the mobile unit moves out of range of one base station, it may connect or “handover” to a new base station and starts communicating with the wired network through the new base station. Infrastructure-based Time Division Multiple Access (TDMA) networks typically employ central scheduling via a central, fixed controller (such as a base station). In these networks, TDMA protocols can be used to assign a timeslot to each flow or user in the network. For example, circuit switched TDMA-based voice systems usually allocate a single timeslot in a frame for a single voice connection for a period of time. By contrast, systems which tend to carry bursty data typically use dynamic allocation schemes to assign timeslots. For instance, Demand Assigned Multiple Access (DAMA) systems can be used to allocate timeslots on demand.
In comparison to infrastructure-based wireless networks, such as cellular networks or satellite networks, ad hoc networks are self-forming networks which can operate in the absence of any fixed infrastructure, and in some cases the ad hoc network is formed entirely of mobile nodes. An ad hoc network typically includes a number of geographically-distributed, potentially mobile units, sometimes referred to as “nodes,” which are wirelessly connected to each other by one or more links (e.g., radio frequency communication channels). The nodes can communicate with each other over a wireless media without the support of an infrastructure-based or wired network. Links or connections between these nodes can change dynamically in an arbitrary manner as existing nodes move within the ad hoc network, as new nodes join or enter the ad hoc network, or as existing nodes leave or exit the ad hoc network. Because the topology of an ad hoc network can change significantly techniques are needed which can allow the ad hoc network to dynamically adjust to these changes. Due to the lack of a central controller, many network-controlling functions can be distributed among the nodes such that the nodes can self-organize and reconfigure in response to topology changes.
One characteristic of the nodes is that each node can directly communicate over a short range with nodes which are a single “hop” away. Such nodes are sometimes referred to as “neighbor nodes.” When a node transmits packets to a destination node and the nodes are separated by more than one hop (e.g., the distance between two nodes exceeds the radio transmission range of the nodes, or a physical barrier is present between the nodes), the packets can be relayed via intermediate nodes (“multi-hopping”) until the packets reach the destination node. In such situations, each intermediate node routes the packets (e.g., data and control information) to the next node along the route, until the packets reach their final destination. For relaying packets to the next node, each node should maintain routing information collected through conversation with neighboring nodes. The routing information can also be periodically broadcast in the network to reflect the current network topology. Alternatively, to reduce the amount of information transmitted for maintaining accurate routing information, the network nodes may exchange routing information only when it is needed. In an approach known as Mesh Scalable Routing (MSR), described in U.S. Patent Publication 20040143842 which is incorporated by reference herein in its entirety, nodes periodically send HELLO messages (e.g., once per second) that contain routing information and metrics associated with a route to a central node. Mobile nodes use information extracted from the HELLO messages to decide the most efficient manner for performing handoff. However, in many cases the HELLO messages are not transmitted in a reliable manner which can affect the efficiency of transmitting routing information, which in turn affects communication reliability.
Wireless local area networks typically use protocols such as IEEE 802.11x or IEEE 802.16 to assign timeslots to nodes in a network.
IEEE 802.11x protocols use a fixed Access Point (AP) that manages the network operations in a manner that is similar to the way base stations manage the operations in cellular wireless networks. Given the dynamic nature of nodes in a ad hoc multi-hopping network, these protocols can not provide efficient resource management. IEEE 802.16 protocols use base stations to assign timeslots to each node. Each node rebroadcasts a “slot allocation matrix” of the network. Centralized allocation of timeslots requires exchanging a large amount of network management information, which consumes valuable communication bandwidth. Centralized timeslot allocation techniques are typically applied in networks where the length of the communication path is relatively small (e.g., only one hop). Applying centralized timeslot allocation techniques in multi-hopping networks can be problematic because the of the significant amount of time required for propagating information from nodes at the periphery of the network to a central node, and for propagating information from the central node back to the nodes at the periphery of the network. Centralized timeslot allocation techniques are inefficient for reaching all network nodes due to mobility of nodes and the relatively long time needed for propagating the information to each node in the network. For this reason, in mobile multi-hopping networks, where the topology of nodes changes frequently, the utilization of centralized timeslot allocation techniques is prohibitive.
Current TDMA-based wireless networks are generally designed for transporting voice data using a particular modulation and relative low data rate. However, the techniques used in these networks cannot easily be applied to systems transporting time sensitive data such as interactive voice/video and non-interactive data such as one way audio/video at variable modulation and high data rates.
The protocols for timeslot allocation discussed above can be used in infrastructure based networks, but do not perform well or can even fail in ad hoc, multi-hopping networks where the node positions and data rate for each link change dynamically.
Skilled artisans will appreciate that elements in the figures are illustrated for simplicity and clarity and have not necessarily been drawn to scale. For example, the dimensions of some of the elements in the figures may be exaggerated relative to other elements to help to improve understanding of embodiments of the present invention.